home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Utilities / byacc 1.8.2 / mkpar.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-04  |  7.5 KB  |  411 lines  |  [TEXT/R*ch]
  1. #include "defs.h"
  2.  
  3. action **parser;
  4. int SRtotal;
  5. int RRtotal;
  6. short *SRconflicts;
  7. short *RRconflicts;
  8. short *defred;
  9. short *rules_used;
  10. short nunused;
  11. short final_state;
  12.  
  13. static int SRcount;
  14. static int RRcount;
  15.  
  16. static action *parse_actions _P_((register int stateno));
  17. static void find_final_state _P_((void));
  18. static void remove_conflicts _P_((void));
  19. static void unused_rules _P_((void));
  20. static void total_conflicts _P_((void));
  21. static void defreds _P_((void));
  22. static action *get_shifts _P_((int stateno));
  23. static action *add_reductions _P_((int stateno, register action *actions));
  24. static action *add_reduce _P_((register action *actions,
  25.                    register int ruleno,
  26.                    register int symbol));
  27.  
  28. #if __STDC__
  29. void make_parser(void)
  30. #else
  31. void make_parser()
  32. #endif
  33. {
  34.     register int i;
  35.  
  36.     parser = NEW2(nstates, action *);
  37.     for (i = 0; i < nstates; i++)
  38.     parser[i] = parse_actions(i);
  39.  
  40.     find_final_state();
  41.     remove_conflicts();
  42.     unused_rules();
  43.     if (SRtotal + RRtotal > 0) total_conflicts();
  44.     defreds();
  45. }
  46.  
  47.  
  48. #if __STDC__
  49. static action *parse_actions(register int stateno)
  50. #else
  51. static action *parse_actions(stateno)
  52. register int stateno;
  53. #endif
  54. {
  55.     register action *actions;
  56.  
  57.     actions = get_shifts(stateno);
  58.     actions = add_reductions(stateno, actions);
  59.     return (actions);
  60. }
  61.  
  62.  
  63. #if __STDC__
  64. static action *get_shifts(int stateno)
  65. #else
  66. static action *get_shifts(stateno)
  67. int stateno;
  68. #endif
  69. {
  70.     register action *actions, *temp;
  71.     register shifts *sp;
  72.     register short *to_state;
  73.     register int i, k;
  74.     register int symbol;
  75.  
  76.     actions = 0;
  77.     sp = shift_table[stateno];
  78.     if (sp)
  79.     {
  80.     to_state = sp->shift;
  81.     for (i = sp->nshifts - 1; i >= 0; i--)
  82.     {
  83.         k = to_state[i];
  84.         symbol = accessing_symbol[k];
  85.         if (ISTOKEN(symbol))
  86.         {
  87.         temp = NEW(action);
  88.         temp->next = actions;
  89.         temp->symbol = symbol;
  90.         temp->number = k;
  91.         temp->prec = symbol_prec[symbol];
  92.         temp->action_code = SHIFT;
  93.         temp->assoc = symbol_assoc[symbol];
  94.         actions = temp;
  95.         }
  96.     }
  97.     }
  98.     return (actions);
  99. }
  100.  
  101. #if __STDC__
  102. static action *add_reductions(int stateno, register action *actions)
  103. #else
  104. static action *add_reductions(stateno, actions)
  105. int stateno;
  106. register action *actions;
  107. #endif
  108. {
  109.     register int i, j, m, n;
  110.     register int ruleno, tokensetsize;
  111.     register unsigned *rowp;
  112.  
  113.     tokensetsize = WORDSIZE(ntokens);
  114.     m = lookaheads[stateno];
  115.     n = lookaheads[stateno + 1];
  116.     for (i = m; i < n; i++)
  117.     {
  118.     ruleno = LAruleno[i];
  119.     rowp = LA + i * tokensetsize;
  120.     for (j = ntokens - 1; j >= 0; j--)
  121.     {
  122.         if (BIT(rowp, j))
  123.         actions = add_reduce(actions, ruleno, j);
  124.     }
  125.     }
  126.     return (actions);
  127. }
  128.  
  129.  
  130. #if __STDC__
  131. static action *add_reduce(register action *actions,
  132.               register int ruleno,
  133.               register int symbol)
  134. #else
  135. static action *add_reduce(actions, ruleno, symbol)
  136. register action *actions;
  137. register int ruleno, symbol;
  138. #endif
  139. {
  140.     register action *temp, *prev, *next;
  141.  
  142.     prev = 0;
  143.     for (next = actions; next && next->symbol < symbol; next = next->next)
  144.     prev = next;
  145.  
  146.     while (next && next->symbol == symbol && next->action_code == SHIFT)
  147.     {
  148.     prev = next;
  149.     next = next->next;
  150.     }
  151.  
  152.     while (next && next->symbol == symbol &&
  153.         next->action_code == REDUCE && next->number < ruleno)
  154.     {
  155.     prev = next;
  156.     next = next->next;
  157.     }
  158.  
  159.     temp = NEW(action);
  160.     temp->next = next;
  161.     temp->symbol = symbol;
  162.     temp->number = ruleno;
  163.     temp->prec = rprec[ruleno];
  164.     temp->action_code = REDUCE;
  165.     temp->assoc = rassoc[ruleno];
  166.  
  167.     if (prev)
  168.     prev->next = temp;
  169.     else
  170.     actions = temp;
  171.  
  172.     return (actions);
  173. }
  174.  
  175.  
  176. #if __STDC__
  177. static void find_final_state(void)
  178. #else
  179. static void find_final_state()
  180. #endif
  181. {
  182.     register int goal, i;
  183.     register short *to_state;
  184.     register shifts *p;
  185.  
  186.     p = shift_table[0];
  187.     to_state = p->shift;
  188.     goal = ritem[1];
  189.     for (i = p->nshifts - 1; i >= 0; --i)
  190.     {
  191.     final_state = to_state[i];
  192.     if (accessing_symbol[final_state] == goal) break;
  193.     }
  194. }
  195.  
  196.  
  197. #if __STDC__
  198. static void unused_rules(void)
  199. #else
  200. static void unused_rules()
  201. #endif
  202. {
  203.     register int i;
  204.     register action *p;
  205.  
  206.     rules_used = (short *) MALLOC(nrules*sizeof(short));
  207.  
  208.     for (i = 0; i < nrules; ++i)
  209.     rules_used[i] = 0;
  210.  
  211.     for (i = 0; i < nstates; ++i)
  212.     {
  213.     for (p = parser[i]; p; p = p->next)
  214.     {
  215.         if (p->action_code == REDUCE && p->suppressed == 0)
  216.         rules_used[p->number] = 1;
  217.     }
  218.     }
  219.  
  220.     nunused = 0;
  221.     for (i = 3; i < nrules; ++i)
  222.     if (!rules_used[i]) ++nunused;
  223.  
  224.     if (nunused)
  225.     if (nunused == 1)
  226.         fprintf(stderr, "%s: 1 rule never reduced\n", myname);
  227.     else
  228.         fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
  229. }
  230.  
  231.  
  232. #if __STDC__
  233. static void remove_conflicts(void)
  234. #else
  235. static void remove_conflicts()
  236. #endif
  237. {
  238.     register int i;
  239.     register int symbol;
  240.     register action *p, *pref;
  241.  
  242.     SRtotal = 0;
  243.     RRtotal = 0;
  244.     SRconflicts = NEW2(nstates, short);
  245.     RRconflicts = NEW2(nstates, short);
  246.     for (i = 0; i < nstates; i++)
  247.     {
  248.     SRcount = 0;
  249.     RRcount = 0;
  250.     symbol = -1;
  251.     for (p = parser[i]; p; p = p->next)
  252.     {
  253.         if (p->symbol != symbol)
  254.         {
  255.         pref = p;
  256.         symbol = p->symbol;
  257.         }
  258.         else if (i == final_state && symbol == 0)
  259.         {
  260.         SRcount++;
  261.         p->suppressed = 1;
  262.         }
  263.         else if (pref->action_code == SHIFT)
  264.         {
  265.         if (pref->prec > 0 && p->prec > 0)
  266.         {
  267.             if (pref->prec < p->prec)
  268.             {
  269.             pref->suppressed = 2;
  270.             pref = p;
  271.             }
  272.             else if (pref->prec > p->prec)
  273.             {
  274.             p->suppressed = 2;
  275.             }
  276.             else if (pref->assoc == LEFT)
  277.             {
  278.             pref->suppressed = 2;
  279.             pref = p;
  280.             }
  281.             else if (pref->assoc == RIGHT)
  282.             {
  283.             p->suppressed = 2;
  284.             }
  285.             else
  286.             {
  287.             pref->suppressed = 2;
  288.             p->suppressed = 2;
  289.             }
  290.         }
  291.         else
  292.         {
  293.             SRcount++;
  294.             p->suppressed = 1;
  295.         }
  296.         }
  297.         else
  298.         {
  299.         RRcount++;
  300.         p->suppressed = 1;
  301.         }
  302.     }
  303.     SRtotal += SRcount;
  304.     RRtotal += RRcount;
  305.     SRconflicts[i] = SRcount;
  306.     RRconflicts[i] = RRcount;
  307.     }
  308. }
  309.  
  310.  
  311. #if __STDC__
  312. static void total_conflicts(void)
  313. #else
  314. static void total_conflicts()
  315. #endif
  316. {
  317.     fprintf(stderr, "%s: ", myname);
  318.     if (SRtotal == 1)
  319.     fprintf(stderr, "1 shift/reduce conflict");
  320.     else if (SRtotal > 1)
  321.     fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  322.  
  323.     if (SRtotal && RRtotal)
  324.     fprintf(stderr, ", ");
  325.  
  326.     if (RRtotal == 1)
  327.     fprintf(stderr, "1 reduce/reduce conflict");
  328.     else if (RRtotal > 1)
  329.     fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  330.  
  331.     fprintf(stderr, ".\n");
  332. }
  333.  
  334.  
  335. #if __STDC__
  336. static int sole_reduction(int stateno)
  337. #else
  338. int sole_reduction(stateno)
  339. int stateno;
  340. #endif
  341. {
  342.     register int count, ruleno;
  343.     register action *p;
  344.  
  345.     count = 0;
  346.     ruleno = 0; 
  347.     for (p = parser[stateno]; p; p = p->next)
  348.     {
  349.     if (p->action_code == SHIFT && p->suppressed == 0)
  350.         return (0);
  351.     else if (p->action_code == REDUCE && p->suppressed == 0)
  352.     {
  353.         if (ruleno > 0 && p->number != ruleno)
  354.         return (0);
  355.         if (p->symbol != 1)
  356.         ++count;
  357.         ruleno = p->number;
  358.     }
  359.     }
  360.  
  361.     if (count == 0)
  362.     return (0);
  363.     return (ruleno);
  364. }
  365.  
  366.  
  367. #if __STDC__
  368. static void defreds(void)
  369. #else
  370. static void defreds()
  371. #endif
  372. {
  373.     register int i;
  374.  
  375.     defred = NEW2(nstates, short);
  376.     for (i = 0; i < nstates; i++)
  377.     defred[i] = sole_reduction(i);
  378. }
  379.  
  380. #if __STDC__
  381. static void free_action_row(register action *p)
  382. #else
  383. static void free_action_row(p)
  384. register action *p;
  385. #endif
  386. {
  387.   register action *q;
  388.  
  389.   while (p)
  390.     {
  391.       q = p->next;
  392.       FREE(p);
  393.       p = q;
  394.     }
  395. }
  396.  
  397. #if __STDC__
  398. void free_parser(void)
  399. #else
  400. void free_parser()
  401. #endif
  402. {
  403.   register int i;
  404.  
  405.   for (i = 0; i < nstates; i++)
  406.     free_action_row(parser[i]);
  407.  
  408.   FREE(parser);
  409. }
  410.  
  411.